package com.atwulidun.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序完成后为：");
        System.out.println(Arrays.toString(arr));
    }

        public static void quickSort(int[] arr, int left, int right) {
        // 递归返回的条件
        // 出现left == right的情况：
        // 当基准数的左边或右边只有一个数字时
        // 出现left > right的情况：
        // 譬如基准数左边或右边已经没有数字时
        if (left > right) {
            return;
        }
        int l = left;// 定义一个左索引
        int r = right;// 定义一个右索引
        int base = arr[left];// 定义一个基准数
        while (l != r) {
            // 由于基准数取了进行本次排列的最左边的数，因此先由右索引从右往左检索，直到找到一个比基准数小的数才退出循环
            while (arr[r] >= base && l < r) {
                r--;
            }
            // 上面的右索引停下后，左索引就可以启动了，直到找到一个比基准数大的数才退出循环
            while (arr[l] <= base && l < r) {
                l++;
            }
            // 当右左索引都停下来后，交换两个索引所在处的值
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        // 当左右索引相等时，两者都停下来，此时交换基准数和索引相遇处的值
        // 那么基准数左边的数都比基准数小，右边的数都比基准数大
        arr[left] = arr[l];
        arr[l] = base;
        // 左递归
        quickSort(arr, left, l - 1);
        // 右递归
        quickSort(arr, r + 1, right);
    }
}
